package cn.rocky.offer;

import java.util.HashSet;
import java.util.Set;

public class offer38 {
    int N = 10;
    Set<String> set = new HashSet<String>();
    boolean[] vis = new boolean[N];

    public String[] permutation(String s) {
        char[] cs = s.toCharArray();
        dfs(cs, 0, "");
        String[] ans = new String[set.size()];
        int idx = 0;
        for (String str : set) {
            ans[idx++] = str;
        }
        return ans;
    }

    /**
     * 需要返回所有不重复的排列字符串
     * @param cs    原字符串
     * @param u     当前决策到目标字符串的哪一位
     * @param cur   当前目标字符串
     */
    void dfs(char[] cs, int u, String cur) {
        int n = cs.length;
        if (u == n) {
            set.add(cur);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                vis[i] = true;
                dfs(cs, u + 1, cur + String.valueOf(cs[i]));
                vis[i] = false;
            }
        }
    }

    public static void main(String[] args) {

    }
}
